package search.bts;

/**
 * @Author ZhangGJ
 * @Date 2021/01/18 06:51
 */
public class BTS<Key extends Comparable<Key>, Value> {

	private Node root;


	private class Node {
		private Key key;
		private Value value;
		private Node left, right;
		private int n;

		public Node(Key key, Value value, int n) {
			this.key = key;
			this.value = value;
			this.n = n;
		}
	}

	public int size() {
		return size(root);
	}

	public int size(Node x) {
		if (x == null) {
			return 0;
		} else {
			return x.n;
		}
	}

	public Value get(Key key) {
		return get(root, key);
	}

	private Value get(Node x, Key key) {
		if (x == null) {
			return null;
		}
		int cmp = key.compareTo(x.key);
		if (cmp < 0) {
			return get(x.left, key);
		} else if (cmp > 0) {
			return get(x.right, key);
		} else {
			return x.value;
		}
	}

	public void put(Key key, Value value) {
		root = put(root, key, value);
	}

	public Node put(Node x, Key key, Value value) {
		if (x == null) {
			return new Node(key, value, 1);
		}
		int cmp = key.compareTo(x.key);
		if (cmp < 0) {
			x.left = put(x.left, key, value);
		} else if (cmp > 0) {
			x.right = put(x.right, key, value);
		} else {
			x.value = value;
		}
		x.n = size(x.left) + size(x.right) + 1;
		return x;
	}
}
